<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>


  <meta content="text/html; charset=UTF-8" http-equiv="content-type">
  <title>IFT615 / TP1 - Connect5</title>
  <meta content="Éric Beaudry" name="author">
  <meta content="Énoncé du TP1 d'IFT615 - Connect5" name="description">
</head><body>
<h1 style="text-align: center;">IFT615 - Intelligence artificielle<br>
</h1>
<div style="text-align: center;">Département d'informatique<br>
Université de Sherbrooke<br>
<br>
Été 2011<br>
<big><big><span style="font-style: italic; font-weight: bold;">Travail
pratique #1 <br>
</span><small>à remettre le 17
juin 2011</small></big></big><br>
<div style="text-align: left;"><br>
<br>
<h1>1. Introduction<br>
</h1>
</div>
</div>
<span style="font-family: monospace;"></span><span style="font-family: monospace;"></span>Vous devez programmer un joueur
artificiel pour une variante du jeu <span style="font-style: italic; font-weight: bold;">Connect
5</span> (aussi connu sous le nom de <span style="font-style: italic;">Go-Moku</span>).
Il
est
fortement
conseillé
d'implémenter
votre
joueur à l'aide de
l'algorithme <span style="font-weight: bold;">minimax avec élagage
alpha-beta</span> <span style="font-style: italic;">(alpha-beta pruning</span>)
vu
en classe.<br>
<h2>1.1 Règles du jeu</h2>
Les règles du jeu sont les suivantes :<br>
<ul>
  <li>Deux joueurs déposent des pierres les unes à la suite des autres.</li>
  <li>Le premier joueur dépose des pierres noires alors que son
adversaire utilise des blanches.</li>
  <li>Le jeu s'effectue sur une grille d'une dimension arbitraire. Les
pierres doivent être déposées à l'intérieur des cases et non sur les
intersections.</li>
  <li>Pour gagner, un joueur doit aligner <span style="font-weight: bold;">exactement</span> <span style="font-weight: bold;">cinq (5)</span> pierres à l'horizontal, à
la
verticale ou en diagonale.</li>
  <li>Le jeu se termine lorsqu'un joueur gagne la partie ou lorsqu'il
n'y a plus de placement possible (grille complète). Dans le dernier
cas, la partie est déclarée nulle.</li>
</ul>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
  <tbody>
    <tr>
      <td style="vertical-align: top; text-align: center;"><img src="IFT615%20_%20TP1%20-%20Connect5_fichiers/exemple1.png" alt=""></td>
      <td style="vertical-align: top; text-align: center;"><img src="IFT615%20_%20TP1%20-%20Connect5_fichiers/exemple2.png" alt=""></td>
      <td style="vertical-align: top; text-align: center;"><img src="IFT615%20_%20TP1%20-%20Connect5_fichiers/exemple3.png" alt=""></td>
    </tr>
    <tr>
      <td style="vertical-align: top; text-align: center;">Configuration
gagnante<br>
      </td>
      <td style="vertical-align: top; text-align: center;">Configuration
non
gagnante<br>
      </td>
      <td style="vertical-align: top; text-align: center;">Configuration
non
gagnante
puisqu'il<br>
&nbsp;y a 6 et non 5 pierres d'alignées<br>
      </td>
    </tr>
  </tbody>
</table>
<br>
<h2>1.2 Caractéristiques du jeu</h2>
Le jeu <span style="font-style: italic;">Connect 5</span> est un jeu à
l'avantage du joueur qui commence la partie. En d'autres mots, si le
premier joueur ne fait aucune erreur, il a la garantie de gagner la
partie, et ce même si son adversaire joue lui aussi de façon optimale.<br>
<br>
<h1>2. Interface du joueur artificiel<br>
</h1>
Votre programme sera corrigé de façon automatique. S'il ne respecte pas
l'une des interfaces de communication disponibles, votre programme ne
passera pas les tests de correction
automatique et entraînera une note de zéro (0). Vous pouvez
préalablement tester votre programme à l'aide d'un
utilitaire <span style="font-weight: bold;">(</span><a style="font-weight: bold;" href="http://planiart.usherbrooke.ca/%7Eeric/ift615/tp1/ift615-connect5.zip">ift615-connect5.zip</a><span style="font-weight: bold;">)</span>.
Pour lancer l'utilitaire, il suffit de lancer le fichier <span style="font-family: monospace;">Connect5.jar</span> à l'aide de la
commande : « <big style="font-weight: bold; font-family: monospace;">java
-jar
Connect5.jar</big> ».<br>
<br>
<img style="width: 608px; height: 529px;" alt="ift615-connect5.png" src="IFT615%20_%20TP1%20-%20Connect5_fichiers/ift615-connect5.png"><br>
<br>
<span style="font-weight: bold;"><br>
</span>Il existe trois interfaces pour connecter un joueur artificiel à
l'interface <span style="font-style: italic;">Connect5</span>. Le
choix de l'interface désirée est disponible
dans la boîte de configuration de l'outil <span style="font-style: italic;">Connect5</span>.<br>
<br>
<img style="width: 1154px; height: 322px;" alt="interfacechoix.png" src="IFT615%20_%20TP1%20-%20Connect5_fichiers/interfacechoix.png"><br>
<br>
<h2>2.1 Interface interne Java</h2>
L'interface interne est la plus simple. L'utilitaire <span style="font-style: italic;">Connect5</span> est
accompagnée d'un joueur artificiel implémenté dans la classe <big style="font-family: monospace;"><span style="font-weight: bold;">JoueurArtificiel</span></big>
du package <big><span style="font-weight: bold; font-family: monospace;">connect5.ia</span></big>.
Pour
utiliser
cette
interface,
vous
n'avez
qu'à télécharger le code source (<a href="http://planiart.usherbrooke.ca/%7Eeric/ift615/tp1/ift615-connect5-src.zip">ift615-connect5-src.zip</a>)
et
modifier la classe JoueurArtificiel. Vous pouvez ajouter d'autres
fichiers
sources dans
le package <big><span style="font-weight: bold; font-family: monospace;">connect5.ia</span></big><span style="font-weight: bold; font-family: monospace;"></span>.
Cependant, vous ne pouvez pas faire d'autres modifications au niveau du
package <big><span style="font-weight: bold; font-family: monospace;">connect5</span></big>.<br>
<br>
<h2>2.2 Interface externe via un appel de processus (ex: exécutable C++)</h2>
Votre programme doit implémenter un protocole de communication très
simple en utilisant l'entrée et la sortie standard (<span style="font-style: italic;">stdin</span> et <span style="font-style: italic;">stdout</span>).
<ol>
  <li>Au démarrage, afficher sur la sortie standard les noms,
matricules et courriels des membres de l'équipe (une ligne par
étudiant).</li>
  <li>Sur une nouvelle ligne, écrire le mot « <big><span style="font-family: monospace;">READY</span></big> ».</li>
  <li>Lire une ligne sur l'entrée standard.</li>
  <li>Si la ligne commence par un zéro (0), alors terminer l'exécution.</li>
  <li>Sinon, il s'agit de la première ligne d'une configuration du
jeu. Il faut alors lire la configuration du jeu.<br>
  </li>
  <li>Déterminer le prochain coup à jouer à l'intérieur d'un délai de
réflexion donné. Vous devez préalablement compter le nombre de pierres
de chaque couleur afin de déterminer pour quel joueur vous devez jouer.<br>
  </li>
  <li>Écrire les coordonnées où placer la prochaine pierre sur la
sortie standard dans le format suivant : ligne colonne.<br>
  </li>
  <li>Retourner à l'étape 3.<br>
  </li>
</ol>
<h3>Format de description d'une configuration de jeu</h3>
Une configuration s'écrit de la façon suivante:<br>
<ul>
  <li>Sur la première ligne, deux entiers spécifient le nombre de
lignes (<span style="font-style: italic;">L</span>) et de colonnes (<span style="font-style: italic;">C</span>) de la grille du jeu.</li>
  <li>Les <span style="font-style: italic;">L</span> lignes suivantes
contiennent des chaînes de caractères de longueur <span style="font-style: italic;">C</span> spécifiant l'état d'occupation
des cases de la grille de jeu. Les caractères <big><span style="font-family: monospace;">0</span></big> (zéro), <big><span style="font-family: monospace;">B</span></big> et <big style="font-family: monospace;">N</big> représentent respectivement
des cases libres, occupées par des pierres blanches et occupées par des
pierres noires.</li>
  <li>Sur une dernière ligne, le temps de réflexion alloué est donné en
millisecondes.</li>
</ul>
Par exemple, la séquence<br>
<div style="margin-left: 40px;">
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
  <tbody>
    <tr>
      <td style="vertical-align: top;"><big><span style="font-family: monospace;">8 8<br>
      </span><span style="font-family: monospace;">00000000<br>
      </span><span style="font-family: monospace;">000N0000<br>
      </span><span style="font-family: monospace;">000B0000<br>
      </span><span style="font-family: monospace;">00N00000<br>
      </span><span style="font-family: monospace;">00000000<br>
      </span><span style="font-family: monospace;">00000000<br>
      </span><span style="font-family: monospace;">00000000<br>
      </span><span style="font-family: monospace;">00000000<br>
1000</span></big><span style="font-family: monospace;"><br>
      </span></td>
    </tr>
  </tbody>
</table>
<br>
</div>
spécifie la grille suivante<br>
<div style="margin-left: 40px;"><img src="IFT615%20_%20TP1%20-%20Connect5_fichiers/exemple4.png" alt=""></div>
<div style="margin-left: 40px;"><br>
</div>
et un temps de réflexion de 1000 millisecondes (1 seconde).<br>
<br>
Pour vous aider, des exemple de joueurs artificiels écrits en <span style="font-weight: bold;">C++</span> (<a style="font-family: monospace;" href="http://planiart.usherbrooke.ca/%7Eeric/ift615/tp1/joueuraleatoire.cc">joueuraleatoire.cc</a>)
et
<span style="font-weight: bold; text-decoration: line-through;">Java</span><span style="text-decoration: line-through;"> (</span><a style="font-family: monospace; text-decoration: line-through;" href="http://planiart.usherbrooke.ca/%7Eeric/ift615/tp1/JoueurAleatoire.java">JoueurAleatoire.java</a><span style="text-decoration: line-through;">)</span>
sont
fournis.<br>
<br>
<span style="font-weight: bold; text-decoration: underline;">Attention:
les exécutables compilés dans Microsoft Visual Studio ne fonctionnent
pas avec cette interface. Utilisez plutôt le compilateur GNU GCC.</span><br>
<br>
<h2>2.3 Interface par socket TCP/IP<br>
</h2>
L'interface par socket utilise exactement le même protocole que
l'interface par processus. Votre programme n'a qu'à écouter des
connexions sur un port spécifique donné en argement. Voir l'exemple
fourni en Java (<a href="http://planiart.usherbrooke.ca/%7Eeric/ift615/tp1/ServeurJoueurAleatoire.java">ServeurJoueurAleatoire.java</a>)
ou
C#
(<span style="font-style: italic;">un exemple est à écrire</span>).
Votre implémentation doit pouvoir accepter plusieurs connexions
simultanées.<span style="font-style: italic;"></span> Le programme doit
terminer lorsqu'il reçoit « <big style="font-weight: bold; font-family: monospace;">shutdown</big> » au
lieu de la dimension de la grille.<span style="font-style: italic; background-color: rgb(153, 255, 153);"></span><br>
<br>
<h1>3. Contraintes</h1>
<h2>3.1 Temps de réflexion limité</h2>
À partir d'une certaine taille de grille, il n'est pas possible de
faire une exploration complète de l'arbre de recherche. Pour cette
raison, votre joueur artificiel doit être capable d'ajuster son
comportement en fonction du temps de réflexion alloué. Pour cela, vous
devrez élaborer une heuristique afin d'évaluer les feuilles des
branches n'atteignant pas une partie complétée. Vous devez aussi
modifier légèrement l'algorithme <span style="font-style: italic;">alpha-beta
pruning</span> afin que votre joueur puisse prendre des décisions en
temps réel.
La section 6.4 du manuel du cours vous donne quelques idées pour le
faire.
En particulier, on y mentionne l'utilisation de la stratégie <span style="font-style: italic;">iterative deepening</span> vue dans le
cours sur la recherche heuristique. D'autres meilleures stratégies y
sont mentionnées.
Ces stratégies feront que votre algorithme <span style="font-style: italic;">alpha-beta
pruning</span> devienne en quelque sorte <span style="font-style: italic;">anytime</span>.
Dans le jargon en intelligence artificielle, un algorithme <span style="font-style: italic;">anytime</span> est un algorithme qui a
pour
caractéristique de trouver rapidement une première solution et de
continuer sa recherche afin de l'améliorer. L'algorithme termine
lorsque le temps maximal alloué expire ou lorsque l'espace de recherche
est entièrement visité. En d'autres mots, l'algorithme trouve une
solution
<span style="font-style: italic;">en tout temps</span>, d'où le nom <span style="font-style: italic;">anytime.<br>
<br>
<span style="text-decoration: underline;">Exemple d'algorithme
iterative deepening:</span><br>
</span>
<div style="margin-left: 40px;"><span style="font-family: monospace;">termine
=
false;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">int maxprofondeur = 1;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">solution = null;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">while(tempscourant &lt; limite){</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; nouvellesolution =
alphaBeta(-infiny, +infiny, maxprofondeur);</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; if(!termine)
solution = newsolution;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; maxprofondeur++;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">}</span><br style="font-family: monospace;">
<span style="font-family: monospace;">return solution</span><br style="font-family: monospace;">
<br style="font-family: monospace;">
<br style="font-family: monospace;">
<span style="font-family: monospace;">fonction alphabeta(alpha, beta,
profondeur){</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; if(tempscourant
&gt;= limite){</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
stop = true;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
return 0;</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; }</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; if(profondeur == 0)</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
return evaluation();</span><br style="font-family: monospace;">
<span style="font-family: monospace;">&nbsp;&nbsp; ...</span><br style="font-family: monospace;">
<span style="font-family: monospace;">}</span><br>
</div>
<h2>3.2 Langage de programmation</h2>
Vous pouvez utiliser l'un des langages suivants: Java, C++ ou C#. <span style="font-weight: bold;">Cependant, votre projet doit pouvoir
fonctionner sous Linux.</span><br>
<ul>
</ul>
<h2>3.3 Restrictions de réutilisation de code de tierces parties<br>
</h2>
Pour ce projet, vous n'êtes pas autorisés à adapter ou copier en partie
ou en totalité une implémentation du jeu <span style="font-style: italic;">Connect5</span> ou d'un autre jeu
similaire
venant d'une tierce partie. Tout non-respect de cette directive sera
considéré comme du plagiat : la note zéro (0) sera donnée au projet et
le cas sera référé à la Faculté.<br>
<h2>3.4 Limitations techniques</h2>
<ul>
  <li>Votre programme ne peut utiliser qu'un seul fil d'exécution (<span style="font-style: italic;">thread</span>) pour le calcul d'une
solution.<br>
  </li>
  <li>Votre joueur ne peut pas effectuer des calculs
entre deux requêtes. Il doit être en mode d'attente.<br>
  </li>
  <li>Votre joueur ne doit pas conserver en mémoire des informations
entre deux requêtes. D'ailleurs, les joueurs seront exécutés avec une
limite de mémoire de <span style="font-weight: bold;">512 Mo</span>.
Cette limite sera configurée à l'ade de l'option <big style="font-weight: bold;"><span style="font-family: monospace;">-Xmx512m</span></big>
en Java et par <big style="font-weight: bold;"><span style="font-family: monospace;">ulimit</span></big> sous Linux.</li>
</ul>
Tout non respect de ces limitations techniques peuvent entraîner un
mauvais fonctionnement du correcteur automatique et mener à une
discalification au critère C décrit plus bas.<br>
<h1>4. Fichiers à remettre</h1>
Les fichiers à remettre sont:<br>
<ul>
  <li>Les fichiers sources de votre programme. <br>
  </li>
  <li>Votre remise ne doit contenir aucun fichier intermédiaire ou
binaire. Le correcteur compilera votre programme.</li>
</ul>
Selon le langage de programmation et l'interface utilisés, certaines
modalités s'appliquent afin de simplifier la correction.<br>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
  <tbody>
    <tr>
      <td style="vertical-align: top;"><big><span style="font-weight: bold;">Interface interne<br>
(Java)</span></big><br>
      </td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Soumettez
uniquement les sources
sous connect5.ia</span>. N'incluez pas le paquetage connect5. Si vous
les soumettez, ils seront écrasés par la version originale de ces
fichiers !<br>
      <br>
Exemple d'arborescence :<br>
      <div style="margin-left: 40px;"><span style="font-family: monospace;">tp1</span><span style="font-family: monospace;"></span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src/connect5</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src/connect5/ia<br>
      </span><span style="font-family: monospace;">tp1/src/connect5/ia</span><span style="font-family: monospace;">/JoueurArtificiel.java</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src/connect5/ia/</span><span style="font-family: monospace;">...</span><br>
      </div>
      <br>
Les commandes à utiliser : <br>
      <span style="font-family: monospace; font-weight: bold;">cd
tp1/src/</span><br>
      <span style="font-family: monospace; font-weight: bold;">turnin
-c
ift615 -p tp1 connect5/ia</span><br>
      <br>
      </td>
    </tr>
    <tr>
      <td style="vertical-align: top; font-weight: bold;"><big>Interface
par
processus<br>
(C++)<br>
      </big></td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Votre
projet doit pouvoir se
compiler avec
GCC sous Linux et générer un exécutable nommé joueur.</span><br>
      <br>
Exemple d'arborescence :<br>
      <div style="margin-left: 40px;"><span style="font-family: monospace;">tp1</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src/Joueur.cpp</span><br style="font-family: monospace;">
      <span style="font-family: monospace;">tp1/src/Makefile</span><span style="font-family: monospace;"><br>
      </span></div>
      <br>
Les commandes à utiliser : <br>
      <span style="font-family: monospace; font-weight: bold;">cd
tp1/src/</span><br>
      <span style="font-family: monospace; font-weight: bold;">turnin
-c
ift615 -p tp1 *</span><br>
      <span style="font-weight: bold;"><br>
      </span></td>
    </tr>
    <tr>
      <td style="vertical-align: top; font-weight: bold;"><big>Interface
par
socket
(C#)<br>
      </big></td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Vous
devez obtenir l'autorisation préalable du correcteur avant de commencer
à travailler avec le langage C#</span>. Votre projet devra pouvoir
s'exécuter facilement à l'aide de <a href="http://www.mono-project.com/">Mono</a> sous Linux.<br>
      <br>
Un fichier <span style="font-weight: bold; font-style: italic;">lisezmoi.pdf</span>
ou <span style="font-weight: bold; font-style: italic;">lisezmoi.txt</span>
donnant les instructions requises pour
compiler votre projet. Le fichier doit également contenir les noms,
matricules et adresses électroniques de tous les membres de l'équipe.<br>
      <br>
L'exécutable généré doit être nommé serveurjoueur.exe et prendre comme
argument le numéro de port TCP/IP sur lequel accepter des connexion. <span style="font-weight: bold;">Ce programme doit fonctionner uniquement en
mode console et non en mode GUI.</span><br>
      <br>
Exemple d'appel à l'invite de commande:<br>
      <div style="margin-left: 40px;"><span style="font-family: monospace;">serveurjoueur.exe 1199</span><br>
      </div>
      <br>
Les commandes à utiliser : <br>
      <span style="font-family: monospace; font-weight: bold;">cd
tp1/src/</span><br>
      <span style="font-family: monospace; font-weight: bold;">turnin
-c
ift615 -p tp1 *</span><br>
      </td>
    </tr>
  </tbody>
</table>
<br>
Vous devez soumettre votre travail au plus tard le vendredi 17 juin
2011 à
23 h 59. Prévoyez le soumettre en avance en cas de problèmes techniques.<br>
<h1>5. Évaluation</h1>
<span style="font-weight: bold;">Ce projet compte pour 10% de la note
finale.<br>
<br>
</span>La correction s'effectue selon le barème suivant:<br>
<table style="text-align: left;" border="1" cellpadding="2" cellspacing="2">
  <tbody>
    <tr>
      <td style="vertical-align: top;">Critère<br>
      </td>
      <td style="vertical-align: top;">Points<br>
      </td>
      <td style="vertical-align: top;">Description de la correction<br>
      </td>
    </tr>
    <tr>
      <td style="vertical-align: top; text-align: center;">A<br>
      </td>
      <td style="vertical-align: top;">2<br>
      </td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Respect
des règles du jeu</span>.<br>
Ce test vérifie si votre joueur artificiel joue correctement,
c'est-à-dire dans des cases vides.<br>
      </td>
    </tr>
    <tr>
      <td style="vertical-align: top; text-align: center;">B<br>
      </td>
      <td style="vertical-align: top;">3<br>
      </td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Réactions
adéquates à diverses configurations de jeu</span>.<br>
Votre joueur artificiel sera testé sur des cas simples afin de vérifier
s'il répond correctement. Voir fichier DemoCorrecteurB.java pour des
exemples de test.<br>
      </td>
    </tr>
    <tr>
      <td style="vertical-align: top; text-align: center;">C<br>
      </td>
      <td style="vertical-align: top;">5<br>
      </td>
      <td style="vertical-align: top;"><span style="font-weight: bold;">Qualité
des décisions prises par joueur
artificiel et capacité de répondre à l'intérieur des délais alloués</span>*.<br>
Tous les joueurs articiels seront comparés lors d'un tournoi virtuel.
Il est à noter que le serveur planiart.usherbrooke.ca et le joueur
aléatoire participent au tournoi.
Les
joueurs artificiels s'approchant d'un comportement optimal obtiendront
la notre
maximale (5/5).<br>
      <br>
* Les tests seront réalisés avec l'option « Tolérer un retard de 50% du
temps et pénaliser le coup suivant » activée.<br>
      </td>
    </tr>
  </tbody>
</table>
<br>
La qualité du code ainsi que la modularité de votre solution peuvent
être évaluées. Un maximum de 4 points peuvent être retirés pour les cas
jugés problématiques.<br>
<h1>6. Test</h1>
Un joueur artificiel est disponible sur le serveur <span style="font-weight: bold;">planiart.usherbrooke.ca</span> sur le port <span style="font-weight: bold;">1199</span>.<br>
<br>
<br>
<br>
<div style="text-align: center;">(C) Éric Beaudry 2008-2011.<br>
</div>
</body></html>